// https://www.lintcode.com/problem/word-break/

public class Solution {
    /**
     * @param s: A string
     * @param wordSet: A dictionary of words dict
     * @return: A boolean
     */
    public boolean wordBreak(String s, Set<String> wordSet) {
        // write your code here
        if (wordSet.isEmpty()) {
            return s.length() == 0;
        }
        boolean[] dp = new boolean[s.length() + 1];
        Arrays.fill(dp, false);
        dp[0] = true;
        int max_len = 0;
        for (String word : wordSet) {
            if (word.length() > max_len) {
                max_len = word.length();
            }
        }
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 1; j <= Math.min(i, max_len); ++j) {
                if (!dp[i - j]) {
                    continue;
                }
                String ss = s.substring(i - j, i);
                if (wordSet.contains(ss)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}